package leetcode.editor.cn.q1_300.q50;

/**
 * @author qidi
 * @date 2021-12-20 15:50:09
 */
class Q0081_SearchInRotatedSortedArrayIi {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean search(int[] nums, int target) {
            return exist(nums, target, 0, nums.length - 1);
        }

        private boolean exist(int[] nums, int target, int start, int end) {
            if (target > nums[end] && target < nums[start]) return false;
            while (start <= end) {
                if (start == end && nums[end] != target) return false;
                if (nums[start] == target) return true;
                if (nums[end] == target) return true;
                int mid = start + ((end - start) >> 1);
                if (nums[mid] == target) return true;
                if (nums[start] < nums[end]) {
                    // 在 start ~ end 范围内没有旋转
                    if (target < nums[mid]) {
                        start++;
                        end = mid - 1;
                    } else if (target > nums[mid]) {
                        start = mid + 1;
                        end--;
                    } else {
                        start = getStart(nums, start, end);
                    }
                } else if (nums[start] > nums[end]) {
                    // 在 start ~ end 范围内有旋转
                    if (nums[start] < nums[mid]) {
                        // 在 start ~ mid 范围内没有旋转
                        if (target < nums[mid] && target > nums[start]) {
                            // target 在范围内
                            start++;
                            end = mid;
                        } else {
                            start = mid + 1;
                            end--;
                        }
                    } else if (nums[start] > nums[mid]) {
                        // 在 start ~ mid 范围内有旋转
                        if (target < nums[mid] && target < nums[start] || target > nums[mid] && target > nums[start]) {
                            // target 在范围内
                            start++;
                            end = mid;
                        } else {
                            start = mid + 1;
                            end--;
                        }
                    } else {
                        start = getStart(nums, start, end);
                    }
                } else {
                    start = getStart(nums, start, end);
                }
            }

            return false;
        }

        private int getStart(int[] nums, int start, int end) {
            while (start < end) {
                if (nums[start] != nums[start + 1]) break;
                start++;
            }
            return ++start;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0081_SearchInRotatedSortedArrayIi().new Solution();
        System.out.println(solution.search(new int[]{1, 1}, 0));
        System.out.println(solution.search(new int[]{2, 2, 2, 0, 0, 1}, 0));
        System.out.println(solution.search(new int[]{1}, 0));
        System.out.println(solution.search(new int[]{0, 0, 1, 1, 2, 0}, 2));
        System.out.println(solution.search(new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1}, 2));
        System.out.println(solution.search(new int[]{2, 5, 6, 0, 0, 1, 2}, 0));
        System.out.println(solution.search(new int[]{2, 5, 6, 0, 0, 1, 2}, 3));
    }
}